"""
快速排序
"""

import random as rd


# 数组a，选p为基准，进行分解，小的左边，大的去右边
def Partition(a, p, r, x=None):
    if x is None:
        i = p + 1
    else:
        i = x
    j = r
    x = a[p]
    while (True):
        while a[i] <= x and i < r:  # a[i]<x   左边，第一次停在a[i]>x处
            i = i + 1
        while a[j] >= x and j > p:  # a[j]>x   右边，第一次停在a[j]<x处
            j = j - 1
        if i >= j:  # 这时如果i>=j,说明数组已经分成左右两块
            break
        a[i], a[j] = a[j], a[i]
    a[p] = a[j]
    a[j] = x
    # print(a)
    return j


def QuickSort(a, p, r):
    if p < r:
        q = Partition(a, p, r)
        QuickSort(a, p, q)
        QuickSort(a, q + 1, r)


# 随机选取基准，改进算法
def RandomizedPartiton(a, p, r):
    i = rd.randint(p, r)
    a[i], a[p] = a[p], a[i]
    return Partition(a, p, r)


def RandomizedQuickSort(a, p, r):
    if p < r:
        q = RandomizedPartiton(a, p, r)
        RandomizedQuickSort(a, p, q)
        RandomizedQuickSort(a, q + 1, r)


if __name__ == "__main__":
    a = [0, 0, 0, 0, 0, 0]
    QuickSort(a, 0, len(a) - 1)
    # RandomizedQuickSort(a, 0, len(a) - 1)
    print("sort:", a)
